拜占庭將軍問題

甚麼是拜占庭問題呢？

維基百科的說法如下：

拜占庭將軍問題（Byzantine Generals Problem）是由 Leslie Lamport 提出的在分散是系統中的通訊容錯問題。

在分布式計算中，不同的電腦通過通訊交換資訊達成共識而按照同一套共同作業策略行動。但有時候，系統中的成員電腦可能出錯而傳送錯誤的資訊，用於傳遞資訊的通訊網路也可能導致資訊損壞，使得網路中不同的成員關於全體共同作業的策略得出不同結論，從而破壞系統一致性。拜占庭將軍問題被認為是容錯性問題中最難的問題類型之一。

怕爆...我到底看了甚麼QQ，我們來看看實際的例子好了～

拜占庭問題的問題描述：

拜占庭是古代東羅馬帝國的首都，由於他們是一個很大的帝國，在他們的國內有許多組的軍隊（我們在此假設有 6 組），分別鎮守在不同的位置。

但是，有一天，他們需要攻破一個好像很厲害的城鎮，只要他們同時進攻的人少於 4 組的軍隊，進攻的隊伍就會失敗並且 GG，換句話說，這六個將軍有兩種選擇－一起進攻或是一起撤退－，所以他們必須要想辦法共同決定採取甚麼行動，而這個方法往往就是透過投票（把自己進攻或撤退的意願告訴其他五個將軍），進而達成共識才能取得勝利。

但單純的相信投票結果會出現一個問題，會不會有人是叛徒呢？或者說會不會有人的訊息被惡意修改了呢？

1. 論文中的數學證明：

   在此論文中 Leslie Lamport 證明了＂只要叛徒不超過總人數的 1/3 時，無論如何這共識都一定會被達成，反之，就舞法保證會達成共識了。

2. 此問題和區塊鏈的關係：

   兩者都是在被地方小小軍官或是市民決定的w，也就是為了達成一個分散式系統中的共識，

   • 拜占庭問題：如何在沒有中央統一號令的情況下，去做到各個地方將軍的共識（共同決定）。
   • 區塊鏈：如何在沒有中央帳本的情況下，去做到各個節點的共識。（後文才會詳細提及區塊鏈如何解決這些問題）

3. 和狼人殺的關係（？：

   我讀到這東西的時候就覺得好像和狼人殺很有關係ㄟ，好人方就是好將軍，狼人方就是叛徒，而達成共識就好像是投票放逐的環節xD（雖然兩者還是有一定的落差啦～，不過這應該也就是為甚麼狼人殺的瑯人數會是總人數的1/3吧～

《比特幣：一個點對點的電子現金系統》

區塊鏈這個概念是跟著比特幣一起出現的，在 2008 年，忠本聰發表了一篇《比特幣：一個點對點的電子現金系統》 內提出了比特幣，而這也就是區塊鏈聖經（跪，強烈建議可以去讀一遍喔w。

內文中詳述了是如何去建立這一套點對點式（P2P）的電子交易系統，而不用透過金融機構而直接從某一方傳送，他允許達成共識的雙方可以直接交易而不用透過第三方進行參與，而這交易系統就是比特幣。

參考資料

1. 【羅斯福專欄】拜占庭將軍怎麼打的勝仗？以鋼鐵人為例
2. 【硬塞科技字典】區塊鏈起源於拜占庭時期？什麼是拜占庭問題？
3. 數學一點的拜占庭問題－如何理解拜占庭將軍問題？